package  main.java.leetcode.editor.cn;
//2022-06-14 22:00:06
//给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[1,2,4,7,5,3,6,8,9]
// 
//
// 示例 2： 
//
// 
//输入：mat = [[1,2],[3,4]]
//输出：[1,2,3,4]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// -10⁵ <= mat[i][j] <= 10⁵ 
// 
// Related Topics 数组 矩阵 模拟 👍 356 👎 0

class DiagonalTraverse {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new DiagonalTraverse().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
            int m = mat.length, n = mat[0].length;
            int[] ans = new int[m * n];
            int count = 0;
            for (int i = 0; i < m + n - 1; i++) {
                if ((i & 1) == 0) {
                    //偶数 判断起始位置
                    int x = Math.min(i, m - 1);
                    int y = i - x;
                    //从左下到右上 移动
                    while (y < n && x >= 0) {
                        ans[count++] = mat[x][y];
                        x--;
                        y++;
                    }
                } else {
                    //奇数 判断起始位置
                    int y = Math.min(i, n - 1);
                    int x = i - y;
                    //从右上到左下移动
                    while (x < m && y >= 0) {
                        ans[count++] = mat[x][y];
                        x++;
                        y--;
                    }
                }
            }
            return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
